package com.LeeCode;

import java.util.Arrays;

/**
 * 射箭比赛中的最大得分
 */

public class Code2212 {
    public static void main(String[] args) {
        int numArrows = 89;
        int[] aliceArrows = {3, 2, 28, 1, 7, 1, 16, 7, 3, 13, 3, 5};
        System.out.println(Arrays.toString(new Code2212().maximumBobPoints(numArrows, aliceArrows)));
    }

    private int[] ans;
    private int maxScore = 0;

    public int[] maximumBobPoints(int numArrows, int[] aliceArrows) {
        int[] cur = new int[aliceArrows.length];
        ans = new int[aliceArrows.length];
        backtrace(cur, aliceArrows, 0, numArrows, 0);
        return ans;
    }

    private void backtrace(int[] cur, int[] aliceArrows, int index, int numArrows, int score) {
        if (index == aliceArrows.length) {
            if (score > maxScore) {
                System.arraycopy(cur, 0, ans, 0, ans.length);
                maxScore = score;
                // bobArrows 的总和应当等于 aliceArrows
                if (numArrows > 0) {
                    ans[0] += numArrows;
                }
            }
            return;
        }

        backtrace(cur, aliceArrows, index + 1, numArrows, score);
        if (numArrows > aliceArrows[index]) {
            cur[index] = aliceArrows[index] + 1;
            backtrace(cur, aliceArrows, index + 1, numArrows - cur[index], score + index);
            cur[index] = 0;
        }
    }
}
